def quickpow(a: int, b: int, mod: int):
    """
    即a的b次方模mod
    """
    c = 1
    while b:
        if b & 1:
            c = c * a % mod
        a = a * a % mod
        b >>= 1
    return c


"""
乘法逆元：当mod是素数时，x的乘法逆元就是quickpow(x,mod-2,mod)
"""
